package OptimalAlgorithm.SlidingWindow;
//给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
//对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
//eg:
//输入：s = "ADOBECODEBANC", t = "ABC"
//输出："BANC"
//解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

public class MinWindow {
    public String minWindow(String s, String t) {
        int[] hashT = new int[128];
        int[] hashS = new int[128];
        if (s == null || t == null || s.length() < t.length()) {
            return "";
        }
        int countT = 0;//countT用来表示t字符串中字母的种类
        int countS = 0;//countS用来表示滑动窗口中“有效”的字母种类
        int MinLen = Integer.MAX_VALUE;
        int index = 0;
        for (char c : t.toCharArray()) {
            hashT[c]++;
            if (hashT[c] == 1) {
                countT++;
            }
        }
        for(int left = 0,right = 0;right < s.length();right++){
            int in = s.charAt(right);
            hashS[in]++;//进窗口
            //进窗口后维护一下countS
            if(hashS[in] == hashT[in]){//相等说明这个字母是有效个数了
                countS++;
            }
            //判断
            while (countS == countT){
                //更新结果
                int currentLen = right - left + 1;
                if(MinLen > currentLen){
                    MinLen = currentLen;
                    index = left;
                }
                int out = s.charAt(left);
                //出窗口前维护一下countS
                if(hashS[out] == hashT[out]){//相等说明要出窗口的这个字母将是“无效”个数
                    countS--;
                }
                //出窗口
                hashS[out]--;
                left++;
            }
        }
        if(MinLen == Integer.MAX_VALUE){
            return "";
        }else {
            return s.substring(index,MinLen + index);
        }
    }
}
